package Algorithm.BitOperation;

/**
 * 338. 比特位计数 https://leetcode.cn/problems/counting-bits
 * 题目简述：给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 */
public class CountBits {

    /**
     * 位运算
     */
    public int[] countBits(int n) {
        int[] result = new int[n+1];
        //注意数组越界问题
        if(n <= 0) return result;
        result[0] = 0;
        result[1] = 1;
        for(int i = 2;i < n+1;i++) {
            if(i%2 == 1) {
                //1.奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
                result[i] = result[i-1] + 1;
            } else {
                //2.偶数：二进制表示中，偶数中1的个数一定和除以2之后的那个数一样多。
                //      因为最低位是0，除以2就是右移一位，也就是把那个0抹掉而已，所以1的个数是不变的。
                result[i] = result[i/2];
            }
        }
        return result;
    }
}
